#include<iostream>
#include"Node.h"
using namespace std;
template<typename T>
class List {
private:
	Node<T>* head;
	Node<T>* tail;
	int length;
public:
	List();
	List(const List& tem);
	~List();
	void addNode(T data);
	void ascSort();
	void removeNode(T data);
	T find(T index);
	bool is_empty();
	int sizeList();
	void showList();
	void resShowList();
	void removeAllList();
};
template<typename T>
List<T>::List() {
	this->head = new Node<T>;
	this->tail = new Node<T>;
	this->head->next = this->tail;
	this->tail->prev = this->head;
	this->head->prev = nullptr;
	this->tail->next = nullptr;
	this->length = 0;
}
template<typename T>
List<T>::List(const List& tem) {
	this->head = new Node<T>;
	this->tail = new Node<T>;
	this->head->next = this->tail;
	this->tail->prev = this->head;
	this->head->prev = nullptr;
	this->tail->next = nullptr;
	this->length = 0;
	Node<T>* temp = tem->head;
	while (temp->next!=tem.tail)
	{
		temp = temp->next;
		this->tail->data = temp->data;
		Node<T>* p = new Node<T>;
		this->tail->next = p;
		p->prev = this->tail;
		this->tail = p;
		this->length++;
	}
	this->tail->next = nullptr;
}
template<typename T>
List<T>::~List() {
	if (this->length == 0) {
		delete this->head;
		delete this->tail;
		this->head = nullptr;
		this->tail = nullptr;
		return;
	}
	while (this->head->next!=nullptr)
	{
		Node<T>* temp = this->head;
		this->head = this->head->next;
		delete temp;
	}
	delete head;
	head = nullptr;
}
template<typename T>
void List<T>::addNode(T data) {
	Node<T>* temp = this->tail;
	this->tail->data = data;
	this->tail->next = new Node<T>;
	this->tail = this->tail->next;
	this->tail->next = nullptr;
	this->tail->prev = temp;
	this->length++;
}
template<typename T>
void List<T>::ascSort() {
	if (this->length <= 1) {
		return;
	}
	Node<T>* p = this->head->next;
	for (int i = 0; i < this->length - 1; i++) {
		Node<T>* q = p->next;
		for (int j = i + 1; j < this->length; j++) {
			if (p->data > q->data) {
				T temp = p->data;
				p->data = q->data;
				q->data = temp;
			}
			q = q->next;
		}
		p = p->next;
	}
}
template<typename T>
void List<T>::removeNode(T data) {
	if (this->length == 0) {
		std::cout << "This List is empty!" << endl;
		return;
	}
	Node<T>* p = this->head;
	while (p->next != nullptr) {
		p = p->next;
		if (p->data == data) {
			Node<T>* temp = p->prev;
			temp->next = p->next;
			p->next->prev = temp;
			delete p;
			this->length--;
			return;
		}
	}
}
template<typename T>
T List<T>::find(T index) {
	if (this->length == 0) {
		std::cout << "This List is empty!" << std::endl;
		return NULL;
	}
	if (index > this->length) {
		cout << "index is out of bound!";
		return NULL;
	}
	int x = 0;
	Node<T>* p = nullptr;
	if (x < this->length / 2) {
		p = this->head->next;
		while (p->next != nullptr && x++ != index) {
			p = p->next;
		}
	}
	else
	{
		p = this->tail->prev;
		while (p->prev != nullptr && x++ != index) {
			p = p->prev;
		}
	}
	return p->data;
}
template<typename T>
bool List<T>::is_empty() {
	return this->length == 0;
}
template<typename T>
int List<T>::sizeList() {
	return this->length;
}
template<typename T>
void List<T>::showList() {
	if (this->length == 0) {
		std::cout << "This List is empty!" << std::endl;
		return;
	}
	Node<T>* p = this->head->next;
	while (p != this->tail) {
		std::cout << p->data << std::endl;
		p = p->next;
	}
}
template<typename T>
void List<T>::resShowList() {
	if (this->length == 0) {
		std::cout << "This List is empty!" << std::endl;
		return;
	}
	Node<T>* p = this->tail->prev;
	while (p != this->head) {
		std::cout << p->data << endl;
		p = p->prev;
	}
}
template<typename T>
void List<T>::removeAllList() {
	if (this->length == 0) {
		std::cout << "This List is empty!" << std::endl;
		return;
	}
	Node<T>* p = this->head->next;
	while (p != this->tail) {
		Node<T>* temp = p;
		p = p->next;
		delete temp;
	}
	this->head->next = this->tail;
	this->tail->prev = this->head;
	this->length = 0;
}
int main()
{
	return 0;
}